/* 
 * next permutation
 */

#include "../../func.h"

void nextPermutation(vector<int> &nums)
{
    next_permutation(nums.begin(), nums.end());
}

template <typename BidiIt>
bool next_permutation(BidiIt first, BidiIt last)
{
    const auto rfirst = reverse_iterator<BidiIt>(last);
    const auto rlast = reverse_iterator<BidiIt>(first);

    auto pivot = next(rfirst);

    while (pivot != rlast && *pivot >= *prev(pivot))
        ++pivot;

    if (pivot == rlast)
    {
        reverse(rfirst, rlast);
        return false;
    }

    auto change = find_if(rfirst, pivot, bind1st(less<int>(), *pivot));

    swap(*change, *pivot);
    reverse(rfirst, pivot);

    return true;
}

bool next_permutation2(vector<int> &nums)
{
    int last = nums.size();
    if (last <= 1)
        return false;

    int pivot = last - 1;
    while (pivot > 0 && nums[pivot-1] >= nums[pivot])
        --pivot;

    if (0 == pivot)
    {
        return false;
    }

    int change = last;
    while (change > 0 && nums[change] < nums[pivot-1])
        --change;

    swap(nums[pivot], nums[change]);
    //reverse(&nums[pivot], nums.end());

    return true;
}